"""
33. 搜索旋转排序数组
中等
相关标签
premium lock icon
相关企业
整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。



示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：

输入：nums = [1], target = 0
输出：-1


提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
"""
from bisect import bisect
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """
        主要分为两种情况：中间mid，
        如果left < mid ,说明反转只包括右边，左边依旧是升序,右边大概率分两段升序；
        如果left > mid,说明反转超过了一般，右边是升序吗，左边分两端升序
        :param nums:
        :param target:
        :return:
        """
        def dfs(nums: List[int],left:int,right:int,target:int):
            if left>right:
                return -1
            #检查下是否已经完全升序
            if nums[left]<=nums[right]:
                pos = bisect.bisect_left(nums, target, left, right + 1)
                if pos < len(nums) and nums[pos] == target:
                    return pos
                return -1
            mid = (left + right)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > nums[left]:
                #左边是完全升序,判断target是否在左边，如果在则可通过二分查找
                if target<=nums[mid] and target>=nums[left]:
                    #right+1是因为bisect_left不包含right[left,right)
                    pos = bisect.bisect_left(nums, target,left,mid+1)
                    if pos < len(nums) and nums[pos] == target:
                        return pos
                    return -1
                else:
                    return dfs(nums,mid+1,right,target)
            else:
                #右边mid+1是完全升序,
                if target>=nums[mid+1] and target<=nums[right]:
                    pos = bisect.bisect_left(nums, target,mid+1,right+1)
                    if pos < len(nums) and nums[pos] == target:
                        return pos
                    return -1
                else:
                    return dfs(nums,left,mid-1,target)
        return dfs(nums,0,len(nums)-1,target)


import bisect
if __name__ == '__main__':
    s = Solution()
    nums1 = [4, 5, 6, 7, 0, 1, 2]
    print(s.search(nums1,0))#4
    # nums2 = [4, 5, 6, 7, 0, 1, 2]
    # print(s.search(nums2,3))#-1
    # nums3 = [1]
    # print(s.search(nums3,0))#-1
    # nums3 = [3,1]
    # print(s.search(nums3,1))#1
    # nums3 = [9,0,2,7,8]
    # print(s.search(nums3,1))#1
    # nums3 = [2,3,5,7,1]
    # print(s.search(nums3,6))#1

    # arr = [1, 3, 3, 5, 7]
    # print(bisect.bisect_left(arr, 3))  # 返回 1（第一个3的位置）
    # print(bisect.bisect_left(arr, 4))  # 返回 3（4应插入的位置）
    # print(bisect.bisect_left(arr, 0))  # 返回 0（开头位置）
    # print(bisect.bisect_left(arr, 8))  # 返回 5（末尾位置）
    #
    # arr = [1, 3, 3, 5, 7]
    # print(bisect.bisect_right(arr, 3))  # 3
    # print(bisect.bisect_right(arr, 4))  # 3
    # print(bisect.bisect_right(arr, 0))  # 0
    # print(bisect.bisect_right(arr, 8))  # 5